#include <string.h>

void getNext(char *p, int *next)
{
    int i = 0;
    int j = -1;
    next[0] = -1;
    while (i < strlen(p))
        if (j == -1 || p[i] == p[j])
        {
            i++;
            j++;
            next[i] = j;
        }
        else
        {
            j = next[j];
        }
}
int kmp(char *t, char *p)
{
    int i = 0;
    int j = 0;

    int next[strlen(p) + 1];
    memset(next, 0, sizeof(next));
    getNext(p, next);
    while (i < strlen(t) && j < strlen(p))
    {
        if (j == -1 || t[i] == p[j])
        {
            i++;
            j++;
        }
        else
        {
            j = next[j];
        }
    }

    if (j == strlen(p))
        return i - j;
    else
        return -1;
}